package algorithm.leetcode.I1to100;

import java.util.ArrayList;
import java.util.List;

/**
 * 这题非常好,如果全排列数组不重复的时候一定需要这个searchFromWhere这个参数,表示前一轮用过的数字本轮不再使用
 */


public class Q39 {

    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        recursion(candidates, target, new ArrayList<>(), 0, 0);
        return result;
    }

    private void recursion(int[] candicates,
                           int target,
                           List<Integer> curSolution,
                           int sumSoFar,
                           int searchStartIndex) {
        if (sumSoFar >= target) {
            if (sumSoFar == target) result.add(new ArrayList<>(curSolution));
            return;
        }

        for (int i = searchStartIndex; i < candicates.length; i++) {
            curSolution.add(candicates[i]);
            // 递归从已选的i开始表示允许重复选择当前数字,但是整体在这个for循环框架下,遵循从何处开始则前面的数字不再使用,好好体会
            // 如果是全排列的题,进入递归的开始参数会从i+1开始
            recursion(candicates, target, curSolution, sumSoFar+candicates[i], i);
            curSolution.remove(curSolution.size() - 1);
        }
    }


    public static void main(String[] args) {
        Q39 tn = new Q39();
        int[] cand = {1,7,2,3,5};
        int target = 8;
        List<List<Integer>> res = tn.combinationSum(cand, target);
        System.out.println(res);
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // List<List<Integer>> result = new ArrayList<>();
        dfs(candidates, new ArrayList<>(), 0, target);
        return result;
    }

    public void dfs(int[] candidates,
                    List<Integer> current,
                    int searchFrom,
                    int target) {
        int sum = current.stream().reduce(0, Integer::sum);
        if (sum >= target) {
            if (sum == target) result.add(new ArrayList<>(current));
            return;
        }

        for (int i = searchFrom; i < candidates.length; i++) {
            current.add(candidates[i]);
            dfs(candidates, current, i, target);
            current.remove(current.size()-1);
        }

    }
}
